package cn.wit.sst.ml.kmeans;

import java.util.ArrayList;
import java.util.List;

public class KMeans {

	/** 几个聚类中心 */
	private int k;

	/** 最大迭代次数，避免一直计算不出来稳定的中心点 */
	private int iterations = 100000;

	/** 两点之间的距离计算器，默认计算欧几里得距离 */
	private DistanceStrategy ds;

	/** 计算初始中心点的策略 */
	private CenterStrategy cs;

	public KMeans(int k) {
		this(k, 100);
	}

	public KMeans(int k, int iterations) {
		this.ds = new EuclideanDistanceStrategy();
		//this.cs = new RandomInitialCenterStrategy();
		this.cs = new SimpleCenterStrategy(ds);
		this.k = k;
		this.iterations = iterations;
	}

	/**
	 * K均值聚类算法实现
	 *
	 * @param points - 所有的样本点
	 *
	 * @return 分好的聚类，每个样本点都归入到所属的Cluster
	 */
	public List<Cluster> cluster(List<Sample> points) {
		validate(points, k);

		// 生成初始的随机中心点
		Sample[] centers = cs.getCenters(points, k);

		int iterationCount = 0;				// 迭代次数计算器
		boolean isCenterChanged = true;		// 中心点是否稳定标志
		while ((iterationCount < this.iterations) && isCenterChanged) {
			iterationCount++;

			// 比较每个数据点与聚类中心的距离，就近分配
			List<Cluster> clusters = clusterByCenters(points, centers, ds);

			// 重新计算聚类中心，使用每个类的样本均值作为新的聚类中心
			isCenterChanged = recalculateCenters(clusters, ds);
		}
		List<Cluster> clusters = clusterByCenters(points, centers, ds);

		System.out.println("分成的聚类：" + clusters);

		return clusters;
	}

	/* 校验参数合法性 */
	private void validate(List<Sample> points, int k) {
		if (points.size() == 0) {
			throw new RuntimeException("数据不能为空！");
		}
		if (k == 0) {
			throw new RuntimeException("簇数至少为1！");
		}
	}



	/** 找到距离最近的中心点，将样本点归入该簇 */
	private static void clusterPoint(List<Cluster> clusters, Sample sample, DistanceStrategy ds) {
		double min = Double.MAX_VALUE;
		Cluster targetCluster = null;
		for (Cluster cluster : clusters) {
			double distance = ds.measure(cluster.getCenter(), sample);

			if (min > distance) {
				min = distance;
				targetCluster = cluster;
			}
		}

		targetCluster.getPoints().add(sample);
	}

	/** 根据已有的中心点，将所有的样本点进行分类 */
	private static List<Cluster> clusterByCenters(
			List<Sample> points,
			Sample[] centroids,
			DistanceStrategy ds) {

		List<Cluster> clusters = new ArrayList<>();
		for (Sample centroid : centroids) {
			clusters.add(new Cluster(centroid));
		}

		for (Sample sample : points) {
			clusterPoint(clusters, sample, ds);
		}

		return clusters;
	}

	/** 对已经分好类的簇，通过计算簇内的样本均值，来重新确定中心点 */
	private static boolean recalculateCenters(
			List<Cluster> clusters,
			DistanceStrategy ds) {

		boolean changed = false;
		for (Cluster cluster : clusters) {
			// 簇内一个样本点都没有，就不需要重新计算中心点
			if (cluster.getPoints().size() == 0) {
				continue;
			}

			int sampleSize = cluster.getCenter().size();

			double[] sum = new double[sampleSize];

			for (Sample point : cluster.getPoints()) {
				for (int i = 0; i < sampleSize; i++) {
					sum[i] += point.getAttrs()[i];
				}
			}

			double[] average = new double[sampleSize];
			int count = cluster.getPoints().size();
			for (int i = 0; i < sampleSize; i++) {
				average[i] = sum[i] / count;
			}

			Sample newCenter = new Sample(average);
			// 0.1为精度，如果两个中心点距离<0.1，就认为相等
			if (ds.measure(newCenter, cluster.getCenter()) > 0.1) {
				cluster.setCenter(newCenter);
				changed = true;
			}
		}

		return changed;
	}
}